package com.tlvip.arithmetic.ch01;

import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 * <p>description：大O表示法</p>
 * <p>copyright： copyright(C)2016-2099</p>
 * <p>Life is short,we need passion</p>
 * <p>Summary： </p>
 * <p>instructions： </p>
 * Date 1/23/21</p>
 * Author mac
 *
 * @version 1.0
 */
public class BigO {
    public static void main(String[] args) {
// 1次 O(1)
        int a = 1;

// 3次，是常数阶 算法复杂度是O(1)
        for (int i = 0; i < 3; i++) { // 这里运行4次，在第四次结束
            a = a + 1; // 这里运行3次
        }

        int n = Integer.MAX_VALUE; // 表示n是未知的
        int i = 1;
// 算法复杂度 O(logn)
        while (i <= n) {
            i = i * 2;
        }
// i的值：2,4,8,16...... 2^n,计算次数 x = log2n 计算机里面要忽略常数即：O(logn)

// 算法复杂度 O(nlogn)
        for (int j = 0; j < n; j++) {
            while (i <= n) {
                i = i * 3;
            }
        }

// 运行n次 算法复杂度 O(n)，
// 如果n是已知的，则是O(1)；
        for (i = 0; i < n; i++) {
            a = a + 1;
        }

// 外层运行n次，固定的，内层运行次数如下：
// i = n :1次
// i = n - 1 :2次
// ...
// i = 1运行n次
// 总共：n*(n+1)/2 约等于 n^2 => 算法复杂度O(n^2)
// 注意有个规律，有加减法的时候，找次数最高的那个
// 例如冒泡排序时间复杂度就是这样的
        for (i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                a = a + 1;
            }
        }

        // 空间复杂度
        int data[];
        List<String> list;
        Map map;
        Set set;
        Queue queue;


    }
}
